package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 电话号码的字母组合
 * @date 2025/6/13 12:06
 */
public class LetterCombinations_17 {

    public static void main(String[] args) {
        LetterCombinations_17 letterCombinations17 = new LetterCombinations_17();

        String digits = "23";
//        letterCombinations17.letterCombinations(digits).forEach(System.out::println);
        letterCombinations17.letterCombinations3(digits).forEach(System.out::println);
    }

    /**
     * 个解：回溯
     * <p>
     * 思路：多个集合间找目标组合，每个集合中各取一个元素从而组成目标组合（可通过画出递归树帮助理解、解题）
     */
    private List<String> ans3 = new ArrayList<>();
    private StringBuilder path3 = new StringBuilder();

    public List<String> letterCombinations3(String digits) {
        // 1.不同集合的组合
        // 每个集合各取一个元素；每个集合的元素不能重复使用；目标组合的元素个数=digits长度
        // 先记录每个号码对应的字母集合数组letters[]，遍历时直接取
        // 2.如何在不同集合中，各取一个元素，组成目标组合？
        // 2.1.横向遍历，取第一个集合
        // 通过startNum控制，当前该取哪个号码对应的字母集合letters
        // 通过letters[i]，记录元素
        // 2.2.向下递归，取第二个集合
        // 每个集合元素只用一次
        // 2.3.回溯

        // 递归回溯
        // 1）返回值：void；入参：numLetters，startNum
        // startNum，表示该找哪个号码对应的字母集合
        // 2）递归终止；path.size() == digits.length，则直接记录，并结束本层递归
        // 3）搜索过程；如上
        if (digits == null || digits.isEmpty()) return ans;

        String[] numLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtrack3(numLetters, digits, 0);
        return ans3;
    }

    public void backtrack3(String[] numLetters, String digits, int startNum) {
        // path长度=digits长度，则记录
        if (path3.length() == digits.length()) {
            ans3.add(path3.toString());
            return;
        }

        // 横向遍历
        int startNumIndex = Integer.parseInt(String.valueOf(digits.charAt(startNum)));
        String letters = numLetters[startNumIndex];
        for (int i = 0; i < letters.length(); i++) {
            // 记录
            path3.append(letters.charAt(i));
            // 递归
            // startNum+1，表明取下一个号码；因为每个号码只取一个元素，所以下层递归则要从下一个号码对应的字母集合中取元素
            backtrack3(numLetters, digits, startNum + 1);
            // 回溯
            path3.deleteCharAt(path3.length() - 1);
        }
    }

    /**
     * dmsxl：回溯
     */
    //设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations2(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //迭代处理
        backTracking(digits, numString, 0);
        return list;

    }

    //每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            //递归，处理下一层
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    /**
     * 个解：参考dmsxl-回溯
     * <p>
     * 分析：多个集合间求组合
     * <p>
     * 1.为什么这里不用startIndex，而是digitsIndex？且for循环遍历是从 0 开始，而不是递归传入的index？<br/>
     * 1.1.首先，组合、组合总和 III这两道题使用startIndex，是因为它们都是找同一个集合中的组合，需要通过startIndex知道已经 收获 哪些元素，从而避免得到的组合重复（如{1,2}、{2,1}）；所以进入下一层递归时，for循环起始要从新指定的index开始。<br/>
     * 1.2.然而，该题是分别从多个集合中各找一个元素来形成目标组合，所以digitsIndex的作用只是告知遍历到 原digits 的哪一位数字，确定该从哪个集合取值。而for循环每次都从 0 开始，也是因为每个集合的元素只会使用一次，不同集合之间找组合不会出现重复组合。<br/>
     * 2.为什么不能直接使用path.substring(0, path.length() - 1)？<br/>
     * ——substring()会返回一个String对象，而这里调用函数后没将新的结果更新到path，导致原path其实并没删除元素，从而一直向下递归，从而出现digits越界。<br/>
     */
    // 索引下标与数字对应
    String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    List<String> ans = new ArrayList<>();

    StringBuilder path = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();

        backtrack(digits, 0);
        return ans;
    }

    public void backtrack(String digits, int digitsIndex) {
        // path元素等于digits长度时，表明找到目标组合，记录到ans
        if (path.length() == digits.length()) {
            ans.add(new String(path));
            return;
        }

        // 遍历全部一次记录一次得到的字符串
//        if (digitsIndex == digits.length()) {
//            ans.add(new String(path));
//            return;
//        }

        // 先取到数字对应的所有字母
        char index = digits.charAt(digitsIndex);
        String letter = letters[Integer.parseInt(String.valueOf((index)))];
        // 横向遍历
        for (int i = 0; i < letter.length(); i++) {
            path.append(letter.charAt(i));

            // 向下递归后续数字对应字母
            // digitsIndex + 1，是因为要找后续数字对应的字母（即其它集合）
            backtrack(digits, digitsIndex + 1);

            // 回溯
            // 左闭右开；
            // 为什么path.length() - 1？——因为这里是下标，path.length() - 1指向的是path最后一个字符
            // 为什么path.substring(0, path.length() - 1)会越界？——因为substring()会返回一个String对象，而这里调用函数后没将新的结果更新到path，导致原path其实并没删除元素，从而一直向下递归，导致digits越界
            path = new StringBuilder(path.substring(0, path.length() - 1));
//            path.deleteCharAt(path.length() - 1);
        }
    }

}
